package algorithm;

/**
 * Created by gmwang on 2018/7/24
 */
public class CommonSortAlgorithmUtils {

    static void buildMaxHeap(int[] arr, int lastIndex) {
        // 从最后一个元素的父节点开始进行调整，一直调整到根节点结束
        int j = (lastIndex - 1) / 2;
        while (j >= 0) {
            int rootIndex = j;
            adjustHeap(arr, rootIndex, lastIndex);
            j--;
        }
    }
    static void adjustHeap(int[] arr, int rootIndex, int lastIndex) {//从根节点开始往下调整
        int biggerIndex = rootIndex;
        int leftChildIndex = rootIndex * 2 + 1;
        int rightChildIndex = rootIndex * 2 + 2;
        if(rightChildIndex <= lastIndex){//如果右孩子存在，则左孩子一定存在
            if(arr[rightChildIndex] > arr[rootIndex] || arr[leftChildIndex] > arr[rootIndex]){
                //将子节点更大的元素下标赋值给biggerIndex
                biggerIndex = arr[rightChildIndex] > arr[leftChildIndex]?rightChildIndex:leftChildIndex;
            }
        }
        else if(leftChildIndex <= lastIndex){//保证左孩子存在，且不能越界
            if(arr[leftChildIndex] > arr[rootIndex]){
                biggerIndex = leftChildIndex;
            }
        }
        if(biggerIndex != rootIndex){
            swap(arr, biggerIndex, rootIndex);
            adjustHeap(arr, biggerIndex, lastIndex);
        }
    }
    //交换方法
    static  void swap(int[] data, int i, int j) {
        int tmp=data[i];
        data[i]=data[j];
        data[j]=tmp;
    }
    //
    static void merge(int[] data, int p, int q, int r) {
        int[] B = new int[data.length];
        int s = p;
        int t = q + 1;
        int k = p;
        while (s <= q && t <= r) {
            if (data[s] <= data[t]) {
                B[k] = data[s];
                s++;
            } else {
                B[k] = data[t];
                t++;
            }
            k++;
        }
        if (s == q + 1)
            B[k++] = data[t++];
        else
            B[k++] = data[s++];
        for (int i = p; i <= r; i++)
            data[i] = B[i];
    }

    static Long pastTime(long mills) {
        return System.currentTimeMillis() - mills;
    }
}
